#include <vector>

// 时间复杂度O(N^1.3)
// 空间复杂度O(1)
//非稳定的排序

// 一组一组的进行直接插入排序
// static void shellSort(std::vector<int> &nums)
// {
//     int n = nums.size();
//     // gap > 1进行预排序
//     // gap = 1进行插入排序
//     int gap = n;
//     while (gap > 1)
//     {
//         gap = gap / 3 + 1;
//         for (int i = 0; i < gap; i++)
//         {
//             // [0,end] 插入 end+gap [0, end+gap]有序  -- 间隔为gap的数据
//             for (int j = i; j < n - gap; j += gap)
//             {
//                 int end = j;
//                 int tmp = nums[end + gap];
//                 while (end >= 0 && tmp < nums[end])
//                 {
//                     nums[end + gap] = nums[end];
//                     end -= gap;
//                 }

//                 nums[end + gap] = tmp;
//             }
//         }
//     }
// }

// gap组数据多组依次并排
static void shellSort(std::vector<int> &nums)
{
    int n = nums.size();
    int gap = n;

    while (gap > 1)
    {
        gap = gap / 3 + 1;
        for (int i = 0; i < n - gap; i++)
        {
            int end = i;
            int tmp = nums[end + gap];
            while (end >= 0 && tmp < nums[end])
            {
                nums[end + gap] = nums[end];
                end -= gap;
            }

            nums[end + gap] = tmp;
        }
    }
}